package com.github.yangyishe.p200;

import com.github.yangyishe.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 *
 *
 *
 * 示例 1:
 *
 *
 * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 * 输出：[3,9,20,null,null,15,7]
 * 示例 2:
 *
 * 输入：inorder = [-1], postorder = [-1]
 * 输出：[-1]
 *
 *
 * 提示:
 *
 * 1 <= inorder.length <= 3000
 * postorder.length == inorder.length
 * -3000 <= inorder[i], postorder[i] <= 3000
 * inorder 和 postorder 都由 不同 的值组成
 * postorder 中每一个值都在 inorder 中
 * inorder 保证是树的中序遍历
 * postorder 保证是树的后序遍历
 */
public class Problem106 {
    public static void main(String[] args) {
        int[] inorder=new int[]{9,3,15,20,7};
        int[] postorder=new int[]{9,15,7,20,3};

        Problem106 problem106 = new Problem106();
        TreeNode treeNode = problem106.buildTree(inorder, postorder);
        treeNode.preOrder();

    }

    private Map<Integer,Integer> inVal2IndexMap=new HashMap<>();

    /**
     * 思路:
     * 和根据前序+中序获取树的思路完全一致, 只是后续遍历从最后端获取top节点
     *
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            inVal2IndexMap.put(inorder[i],i);
        }
        return buildTreeNode(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
    }


    public TreeNode buildTreeNode(int[] inorder,int[] postorder,int inStart,int inEnd,int postStart,int postEnd){
        if(inStart==inEnd){
            return new TreeNode(inorder[inStart]);
        }
        int topVal = postorder[postEnd];
        TreeNode topNode = new TreeNode(topVal);
        Integer inTopIndex = inVal2IndexMap.get(topVal);


        if(inStart!=inTopIndex){
            topNode.left=buildTreeNode(inorder,postorder,inStart,inTopIndex-1,postStart,postStart+inTopIndex-1-inStart);
        }
        if(inEnd!=inTopIndex){
            topNode.right=buildTreeNode(inorder,postorder,inTopIndex+1,inEnd,postStart+inTopIndex-inStart,postEnd-1);
        }

        return topNode;
    }

}
